package com.dmall.chapter06.section05;

public class LeetCode200UF {

    private int R, C;
    private char[][] grid;
    private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public int numIslands(char[][] grid) {
        if (grid == null) {
            return 0;
        }

        R = grid.length;
        if (R == 0) {
            return 0;
        }

        C = grid[0].length;
        if (C == 0) {
            return 0;
        }

        this.grid = grid;

        UnionFind unionFind = new UnionFind(grid);
        for (int x = 0; x < R; x++) {
            for (int y = 0; y < C; y++) {
                if (grid[x][y] == '1') {
                    for (int i = 0; i < dirs.length; i++) {
                        int nextx = x + dirs[i][0], nexty = y + dirs[i][1];
                        if (isValid(nextx, nexty)) {
                            int curIndex = x * C + y;
                            int nextIndex = nextx * C + nexty;
                            unionFind.unionElements(curIndex, nextIndex);
                        }
                    }
                }
            }
        }
        return unionFind.getUnionCount();
    }


    private boolean isValid(int x, int y) {
        return x >= 0 && x < R && y >= 0 && y < C && grid[x][y] == '1';
    }

    class UnionFind {
        private int[] rank;
        /** parent[i]表示第i个元素所指向的父节点 */
        private int[] parent;

        private int unionCount;

        UnionFind(char[][] grid) {
            int row = grid.length;
            int col = grid[0].length;
            rank = new int[row * col];
            parent = new int[row * col];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    int index = i * col + j;
                    if (grid[i][j] == '1') {
                        unionCount ++;
                    }
                    parent[index] = index;
                    rank[index] = 1;
                }
            }
        }

        public int getUnionCount() {
            return unionCount;
        }

        /**
         * 查找过程, 查找元素p所对应的集合编号
         * O(h)复杂度, h为树的高度
         * @param p
         * @return
         */
        private int find(int p){
            if (p < 0 || p >= parent.length) {
                throw new IllegalArgumentException("p is out of bound.");
            }

            // path compression 2, 递归算法
            if (p != parent[p]) {
                parent[p] = find(parent[p]);
            }
            return parent[p];
        }

        /**
         * 合并元素p和元素q所属的集合
         * O(h)复杂度, h为树的高度
         * @param p
         * @param q
         */
        public void unionElements(int p, int q) {

            int pRoot = find(p);
            int qRoot = find(q);

            if ( pRoot == qRoot) {
                return;
            }
            unionCount --;
            // 根据两个元素所在树的rank不同判断合并方向
            // 将rank低的集合合并到rank高的集合上
            if (rank[pRoot] < rank[qRoot]) {
                parent[pRoot] = qRoot;
            } else if(rank[qRoot] < rank[pRoot]) {
                parent[qRoot] = pRoot;
            } else {
                // rank[pRoot] == rank[qRoot]
                parent[pRoot] = qRoot;
                // 此时, 我维护rank的值
                rank[qRoot] += 1;
            }
        }
    }

    public static void main(String[] args) {
        char[][] grid = {
                {'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}
        };
        LeetCode200UF leetCode200UF = new LeetCode200UF();
        System.out.println(leetCode200UF.numIslands(grid));
    }
}
